Yosupo Point Set Range Sort Range Composite 题解

Problem link.

先从本题的弱化讲起，也就是，若只有在线区间排序（不是前后缀排序），在线单点查询，怎么做？会做这个自然本题就会了。前置知识：odt（颜色段均摊），线段树合并，线段树分裂。

首先有一个较为清新的想法：用 odt 维护值域单调段。也就是说，odt 上的一段区间 $[l, r)$ 表示此时，$a_l, a_{l + 1}, \dots, a_{r - 1}$ 是单调递增/递减的，具体是递增还是递减可以再开一个大小为 $n$ 的数组 $dec$，存储以 $l$ 开头的那个连续段是递增还是递减（如果连续段不以 $l$ 开头，则 $dec_l$ 的值不重要，可以随便赋一个值）。

这样，一个区间排序，在 odt 上的表现就是先分裂两个区间，然后把 $[l, r)$ 包含的区间合并成一个大区间。于是问题就转化成，如何用一个数据结构维护 odt 上一个区间内具体的值，支持分裂与合并。更具体地，由于一个区间内的值是单调的，只需要支持，将数据结构按照第 $k$ 大分裂成两个数据结构，一个维护前 $k$ 大的数，另一个维护剩下的数。

我们发现动态开点线段树正好符合这个功能。线段树的分裂和合并正好可以维护刚才所说的问题。于是问题便解决了！

再来看复杂度，不妨记 $w = \log V$（$V$ 是数列 $a$ 的值域）。一次线段树分裂花费 $\Theta(w)$ 的时间，增加了不超过 $w$ 个节点。一次区间排序，odt 上只耗费两次分裂，因此每次区间排序只增加 $O(w)$ 个节点，对于整个算法流程，就是增加了 $O(qw)$ 个节点。对于线段树合并，其复杂度是均摊的，具体来说，若某次合并花费 $\Theta(x)$ 的时间，那么线段树会减少 $\Theta(x)$ 个节点。因此若整个算法流程中，线段树出现了 $\Theta(m)$ 个节点，则线段树合并的复杂度为 $O(m)$。初始所有线段树共有 $\Theta(nw)$ 个节点，分裂增加 $O(qw)$ 个节点，因此线段树合并部分的总复杂度为 $O[(n+q)w]$。

总的来看，就是 odt 花费 $O(q\log n)$ 的时间，线段树部分花费 $O[(n+q)\log V]$ 的时间。总复杂度为为线性对数，完全可以接受。实际上常数有点大，所以本题跑得比较慢。

现在来讲讲 range sort range composite 怎么做。其实会了上面的思路剩下的不难。

首先还是用动态开点线段树加 odt 维护序列，不过此时动态开点线段树显然要多维护一下这整个区间的元素的乘积，这个是容易做到的。

再开一棵普通线段树 $t$！这棵线段树和之前所说的 $dec$ 数组很像啊。就是，$t_l$ 表示 odt 上以 $l$ 开始的区间的元素的乘积（也就是这个区间对应动态开点线段树维护的乘积）。如果没有以 $l$ 开始的区间，就把 $t_l$ 设置为单位元。

对于区间查询 $[l, r)$，就先在 odt 上分裂出需要查询的区间（但是不要合并），然后在 $t$ 上查询 $[l, r)$ 的乘积就行了，这么做的正确性显然。

单点修改是容易做到的，这里就不说了。

复杂度的话，由于只是加了个线段树，所以复杂度没有变化，仍然是单 $\log$，很好。

不过需要注意的是，由于维护的元素乘法不一定有交换律，所以动态开点线段树应当拥有一个整体翻转功能，也就是将线段树由升序变为降序，用来应对合并两个单调性不一样的区间的情况。这样才能保证合并的时候元素顺序正确。

参考代码：

• https://judge.yosupo.jp/submission/217046
• 这个链接可以查看仍在维护更新的版本：https://github.com/robinyqc/yosupo-sol/blob/main/solutions/datastructure/point_set_range_sort_range_composite/sol0.cpp